package 算法练习;

import java.util.Scanner;

/**
 * 
 * @author ：soulstones
 * @version ：2019年9月11日 下午10:38:22 @Description：
 * 
 * 
 * 
 */
public class 连续子数组最大和1动态规划 {
	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] arr = new int[n];

		for (int i = 0; i < n; i++) {
			scanner.nextLine();
			arr[i] = scanner.nextInt();
		}
		System.out.println(maxValue(arr));
	}

	public static int maxValue(int[] arr) {
		int n = arr.length;
		// 创建数组dp,大小为arr数组的大小
		int[] dp = new int[n];

		// dp[i]表示从arr[0]到arr[i]的最大和
		dp[0] = arr[0];

		int maxValue = dp[0];
		for (int i = 1; i < n; i++) {
			// dp[i]的值可能为dp[i-1]+arr[i],也可能为arr[i]，取最大值
			dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
			if (dp[i] > maxValue) {
				maxValue = dp[i];
			}
		}
		return maxValue;
	}
}
